/*
 * Copyright (c) 1997, 1998, 2003, 2006 Aleksandar Samardzic
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef TREE_H
#define TREE_H

#include "stack.h"

/* TreeNode class */
typedef struct _PTreeNode {
	void           *pItem;
	struct _PTreeNode *pParent;
	struct _PTreeNode *pNext;
	int             numChildren;
	struct _PTreeNode *pFirstChild,
	               *pLastChild;
} PTreeNode;

/* Tree class */
typedef struct _PTree {
	PTreeNode      *pRoot;
} PTree;

/* AddMode class */
typedef enum { SIBLING, CHILD } PAddMode;

/* Tree class public opertions */
void            Tree_Init(PTree *);
void            Tree_Clean(PTree *);
PTreeNode      *Tree_AddItem(PTree *, void *, PTreeNode *, PAddMode);

/* TreePreorderIterator class */
typedef struct _PTreePreorderIterator {
	PTree          *pTree;
	PStack          stack;
} PTreePreorderIterator;

/* TreePreorderIterator class public opertions */
void            TreePreorderIterator_Attach(PTreePreorderIterator *,
					    PTree *);
int             TreePreorderIterator_Next(PTreePreorderIterator *,
					  void **);

/* TreeRightIterator class */
typedef struct _PTreeRightIterator {
	PTree          *pTree;
	PTreeNode      *pCurr;
} PTreeRightIterator;

/* TreeRightIterator class public opertions */
void            TreeRightIterator_Attach(PTreeRightIterator *,
					 PTreeNode *);
int             TreeRightIterator_Next(PTreeRightIterator *, void **);

/* TreeUpIterator class */
typedef struct _PTreeUpIterator {
	PTree          *pTree;
	PTreeNode      *pCurr;
} PTreeUpIterator;

/* TreeUpIterator class public opertions */
void            TreeUpIterator_Attach(PTreeUpIterator *, PTreeNode *);
int             TreeUpIterator_Next(PTreeUpIterator *, void **);

#endif
